package leetcode_acm.leetcode_1;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月17日 13:59
 */
public class LowestCommonAncestor {
    private class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    //定义递归函数:在root为根的树上寻找p和q的公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        TreeNode small = null,large = null;
        if(p.val > q.val){
            large = p;
        }else{
            small = q;
        }
        return find(root,small,large);
    }

    private TreeNode find(TreeNode root,TreeNode small,TreeNode large){
        if(root == null){
            return null;
        }
        if(small.val <= root.val && root.val <= large.val){
            return root;
        }
        if(small.val > root.val && large.val > root.val){
            return find(root.right,small,large);
        }
        return find(root.left,small,large);
    }




}
